#include<iostream>
#include<vector>
#include<stack> 
using namespace std;

// 打印数组R
void disp(vector<int> &R, int low, int high)
{
	for (int i=low; i<=high; i++)
		printf("%d ",R[i]);
	printf("\n");
}

// 划分算法1
int Partition1(vector<int> &R, int s, int t)
{
	// 记录要排序的范围
	int i=s, j=t;
	
	// 以表首元素为基准
	int base=R[s];
	
	// 从表两端交替向中间遍历,直至i=j为止
	while (i < j)
	{
		// 从后向前遍历, 找一个小于等于基准的R[j]
		while (j>i && R[j]>=base)
			j--;	
		
		if (j>i)
		{
			R[i]=R[j]; // R[j]前移覆盖R[i]
			i++;
		}
		
		// 从前向后遍历,找一个大于基准的R[i]
		while (i<j && R[i]<=base)
			i++;	
		
		if (i<j)
		{
			R[j]=R[i]; // R[i]后移覆盖R[j]
			j--;
		}
	}
	
	// 基准归位
	R[i]=base;
	
	// 返回归位的位置
	return i;
}

// 划分算法2
int Partition2(vector<int> &R, int s, int t)
{
	// 记录要排序的范围
	int i=s, j=s+1;
	
	// 以表首元素为基准
	int base = R[s];
	
	// j从s+1开始遍历其他元素
	while (j <= t)
	{
		// 找到小于等于基准的元素R[j]
		if (R[j]<=base)
		{
			// 扩大小于等于base的元素区间
			i++;	
			
			// 将R[i]与R[j]交换
			if (i!=j)
				swap(R[i], R[j]);
		}
		
		// 继续扫描
		j++;	
	}
	
	// 将基准R[s]和R[i]进行交换
	swap(R[s], R[i]);
	
	// 返回归位的位置
 	return i;
}

/* 递归算法 */
// 对R[s..t]的元素进行快速排序
void QuickSort11(vector<int> &R, int s, int t)	
{
	// 表中至少存在两个元素的情况
	if (s < t)
	{
		// 可以使用前面2种划分算法中的任意一种
		int i = Partition1(R,s,t);
		
		// 打印
		printf("划分结果:"); disp(R,s,t);
		
		// 对左子表递归排序
		QuickSort11(R,s,i-1);
		
		// 对右子表递归排序
		QuickSort11(R,i+1,t);
	}
}

// 递归算法：快速排序
void QuickSort1(vector<int> &R)
{
	int n = R.size();
	QuickSort11(R,0,n-1);
}

/* 非递归算法 */

// 栈元素类型
struct SNode
{
	// 记录要排序的范围
	int low;
	int high;
	
	// 构造函数
	SNode() {}
	
	// 重载构造函数
	SNode(int l,int h):low(l),high(h) {}
};

// 非递归算法：快速排序
void QuickSort2(vector<int> &R)
{
	// 定义一个栈
	stack<SNode> st;	
	
	// 获取数组大小
	int n = R.size();
	
	// 进栈
	st.push(SNode(0, n-1));
	
	// 栈不空循环
	while(!st.empty())
	{
		// 出栈元素e
		SNode e = st.top();
		st.pop();
		
		// 要排序的范围合法
		if(e.low < e.high)
		{
			// 可以使用前面2种划分算法中的任意一种
			int i = Partition1(R,e.low, e.high);
			
			// 子问题1进栈
			st.push(SNode(e.low, i-1));
			
			// 子问题2进栈
			st.push(SNode(i+1,e.high));
		}
	}
}

int main() 
{
	// 初始化数组
	vector<int> a={2,5,1,7,10,6,9,4,3,8};

	// 计算数组大小
	int n = a.size();
	
	// 打印
	printf("排序前: ");
	disp(a, 0, n-1);
	
	// 快速排序
	QuickSort2(a);
	
	// 打印
	printf("排序后: "); 
	disp(a, 0, n-1); 
	return 0;
}
	

